import java.util.*;

/**
 * 1042. 不邻接植花
 * https://leetcode-cn.com/problems/flower-planting-with-no-adjacent/
 */
public class Solutions_1042 {
    public static void main(String[] args) {
//        int N = 3;
//        int[][] paths = {{1, 2}, {2, 3}, {3, 1}};  // output: {1, 2, 3}

        int N = 4;
        int[][] paths = {{1, 2}, {3, 4}};  // output: {1, 2, 1, 2}

//        int N = 4;
//        int[][] paths = {{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 3}, {2, 4}};
        // output: {1, 2, 3, 4}

//        int N = 1;
//        int[][] paths = {};  // output: {1}

        int[] result = gardenNoAdj(N, paths);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法二：数组方式实现（6ms）
     */
    public static int[] gardenNoAdj(int N, int[][] paths) {
        int[] res = new int[N];
        if (paths.length < 1) {
            // 每个花园都没有与其相通的花园，那么直接种第 1 朵花
            Arrays.fill(res, 1);
            return res;
        }
        // 记录花园可以到达哪些花园（每个花园最多可以与 3 个花园互通）
        int[][] map = new int[N + 1][3];
        // indexes[2] = 2，表示花园 2，在 map 中记录与其相邻花园的索引位置
        // indexes[2] = 2，说明在 map[2][2] 索引上记录值
        int[] indexes = new int[N + 1];
        for (int[] path : paths) {
            int x = path[0], y = path[1];
            // x 花园可以到 y 花园，y 花园也可以到 x 花园
            map[x][indexes[x]++] = y;
            map[y][indexes[y]++] = x;
        }
        // 种花
        for (int i = 1; i <= N; i++) {
            // 数组 to 中大于 0 的值，即代表与花园 i 互通的花园
            int[] to = map[i];
            // 1，2，3，4，总共 4 种花
            for (int j = 1; j <= 4; j++) {
                boolean flag = true;
                // 循环判断第 j 种花，是否可以种（即与其互通的全部花园中，都未种上第 j 种花）
                for (int k = 0; k < indexes[i]; k++) {
                    if (res[to[k] - 1] == j) {
                        // 与花园 i 互通的 to[k] 花园上，若种上了第 j 种花，
                        // 那么再判断第 j + 1 种花，是否可以种
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    // 第 j 种花，可以种在花园 i 中
                    res[i - 1] = j;
                    // 继续为下一花园“种花”
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 解法一：Set 集合实现（36ms）
     */
    public static int[] gardenNoAdj1(int N, int[][] paths) {
        int[] res = new int[N + 1];
        // 记录花园可以到达哪些花园
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] path : paths) {
            // path[0] 可以到达 path[1]
            Set<Integer> set = map.getOrDefault(path[0], new HashSet<>());
            set.add(path[1]);
            map.put(path[0], set);
            // path[1] 可以到达 path[0]
            Set<Integer> set2 = map.getOrDefault(path[1], new HashSet<>());
            set2.add(path[0]);
            map.put(path[1], set2);
        }
        // 种花
        for (int i = 1; i <= N; i++) {
            // 花园可以种 1，2，3，4 种花，其中的一朵
            // 不能与互相连通的花园种相同的花
            boolean[] flowers = new boolean[5];
            Set<Integer> set = map.get(i);
            if (set == null) {
                // 没有与其相邻的花园，可以随意种
                res[i] = 1;
                continue;
            }
            for (int garden : set) {
                // 互相连通的花园，种的是什么花
                int flow = res[garden];
                // 互相连通的花园种的花，i 花园不可再种，标记为 true
                flowers[flow] = true;
            }
            for (int j = 1; j <= 4; j++) {
                // 1,2,3,4，若某一朵没有被标记为 true，说明可以种在 i 花园中
                if (!flowers[j]) {
                    res[i] = j;
                    break;
                }
            }
        }
        return Arrays.copyOfRange(res, 1, N + 1);
    }
}
